1. Field of the Invention
The present invention relates to the fields of distributed computer systems, client-server computing and object oriented programming. Specifically, the present invention is a method and apparatus for a client process to determine whether two objects are equivalent objects having particular application to implementing object oriented programming on distributed computer systems based on the client-server model.
2. Background
In an object oriented system, an object is a component comprising data and operations which can be invoked to manipulate the data. The operations are invoked on the object by sending calls to the object. Each object has an object type. The object type defines the object operations that can be performed on objects of that particular object type. The object operations are implemented independent of the objects themselves. Additionally, one object type may inherit the object operations defined and implemented for other object types. For further description on object-oriented design and programming techniques, see B. Meyer, Object-oriented Software Construction, (Prentice Hall, 1988).
In client-server computing, typically there is a set of computers that can communicate with one another through a network connecting the computers. Some of these computers act as providers of functionality to other computers. The providers of functionality are known as servers, the consumers of functionality are known as clients. However, the client-server model also generalizes to the case where distinct programs are running on the same computer. These distinct programs communicate with one another through a protected mechanism, and act as providers and consumers of functionality. For further description of client-server computing, see J. K. Ousterhout et al, Medusa: An experiment in distributed operating system structure, Communications of the ACM 23(2), 1980; R. M. Needham and A. J. Herbert, The Cambridge Distributed Computing System, (Addison-Wesley, 1982); and J. K. Ousterhout et al, The Sprite distributed operating system, IEEE Computer, 1988.
In an object oriented distributed systems based on the client-server model, typically there are servers that provide object oriented interfaces to their clients. That is, these servers support objects comprising data and associated operations. Clients may obtain access to these objects and may execute calls on them. These calls are transmitted from the client to the server. At the server, these calls are executed via the operations associated with the objects. The results of these calls are then transmitted back to the client. For further description of object oriented distributed systems, see E. D. Lazowska et al, The Eden System: A Technical Review, IEEE Transactions on Software Engineering SE-11(1), January 1985; Jul et al, Fine grained mobility in the Emerald System, ACM Transactions on Computer Systems, 6(1), 1988; and B. Liskov, Distributed programming in Argus, Communications of the ACM, 31(3), 1988.
Client programs are typically given object handles to reference particular objects. The object handle provides a way of locating the object and of executing calls upon it. In some systems, the object handles are designed such that a client can only obtain an object handle for a given object from the server or from an existing client. The server will only execute calls that are issued on valid object handles and the server may take care to only issue object handles to clients whom it has verified and are indeed permitted to access the underlying object. Typically, if one client has a secure handle then it can pass this handle on to other programs which it trusts. The other clients then share the same access to the underlying object that the first program had. For further descriptions of distributed systems based on secure handles, see A. D. Birrell and R. M. Needham, A Universal File Server, IEEE Transactions on Software Engineering, S-6(5), 1980, and S. J. Mullender et al, Amoeba--A Distributed Operating System for the 1990s, IEEE Computer, 23(5), 1990.
In an object oriented distributed systems based on the client-server model and secure handles, if a client is given two handles, it may wish to determine if these handles both reference the same underlying object. For example, it may wish to perform loop detection when it is navigating through a graph of related objects. The simple solution is for the client to compare the two handles. If the handles are identical, then the objects are equivalent. Unfortunately such a simplistic notion of equivalence is not really satisfactory. Typically, it is desirable to be able to use a variety of different handle formats in different situations. It may be that even though the two handles have different values, they do in fact reference the same object. In another situation, the two handles may reference distinct objects of a given server, but the server would prefer the distinct objects be treated as equivalent. In yet another situation, the two handles may reference distinct objects of distinct servers, but the distinct servers are cooperating servers and they would prefer the two objects to be treated as equivalent.
The notion of object equivalence is really a semantic notion whose truth can only be determined by the server(s) that implement the objects. It cannot be definitively answered by the client nor by the object invocation and transport mechanism. A server might support several different notions of equivalence, such as "loop detection equivalence", "exact equivalence", "locality equivalence", to be applied in different situations.
For example, consider a collection of objects that implement nameservers. These nameservers are collected into a directed graph. Different clients have different access rights to particular nameservers. So different clients are given handles on different objects that encapsulate different access to the same underlying state. Some of the nameservers might exist as replicated services running on a number of different hosts. So different clients might have handles that refer them to different servers of the replica set. But for loop detection purposes, it may be desirable to treat the different replicas or different access rights to a particular nameserver as representing the "same" object.
Thus, it is desirable to involve the implementing servers in determining whether two objects are equivalent based on their handles. The easiest mechanism would be to provide a server with both handles, including the handle of an object implemented by another server. Unfortunately, a fatal difficulty arises in decentralized and distributed systems. It may be that one of the two handles is in fact a handle that grants privileged access to a protected resource. That is, a handle may be acting as a capability such that mere possession of the handle grants power. In that case, the objects, and their server's security may be compromised by a malicious client.
As will be described, the present invention overcomes the disadvantages of the prior art, and provides a method and apparatus for a client process to securely determine whether two objects are equivalent, without compromising the objects and their server(s) security.